package string.滑动窗口;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 找到字符串中所有字母异位词438.java
 * @createTime 2022年07月27日 14:51:00
 */
public class 找到字符串中所有字母异位词438 {
    public List<Integer> findAnagrams(String s, String p) {
        //窗口
        HashMap<Character, Integer> winodw = new HashMap<>();
        //目标字符串中字符和字符串个数
        HashMap<Character, Integer> target = new HashMap<>();
        for (char c : p.toCharArray()) {
            target.put(c, target.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = 0;
        //符合的数量
        int valide = 0;

        ArrayList<Integer> position = new ArrayList<>();
        //扩大窗口
        while (right < s.length()) {
            Character c = s.charAt(right);
            right++;
            if (target.containsKey(c)) {
                winodw.put(c, winodw.getOrDefault(c, 0) + 1);
                if (winodw.get(c).equals(target.get(c))) {
                    valide++;
                }
            }
            //是否需要缩小窗口
            while (right - left >= p.length()) {
                //满足异位词的时候则记录下来
                if (valide == target.size()) {
                    position.add(left);
                }
                Character c1 = s.charAt(left);
                left++;
                if (target.containsKey(c1)) {
                    if (winodw.get(c1).equals(target.get(c1))) {
                        valide--;
                    }
                    winodw.put(c1, winodw.get(c1) - 1);
                }
            }
        }
        return position;
    }
}
